package com.datastructure.test.isentirebinarytree;

import java.util.LinkedList;

public class IsEntireBinaryTree {
    public static void main(String[] args) {

    }

    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root == null) {
            return true;
        }

        // 使用层序遍历的思路，进行遍历，只是不需要判断left和right是否为null
        // 如果前面出现了null，后面又有非null的情况，那么就不是完全二叉树
        LinkedList<TreeNode> list = new LinkedList();
        list.offer(root);
        boolean hasNull = false;
        while (!list.isEmpty()) {
            TreeNode currentNode = list.poll();
            if (currentNode == null) {
                hasNull = true;
            } else {
                if (hasNull) return false;

                list.offer(currentNode.left);
                list.offer(currentNode.right);
            }
        }

        return true;}

}

class TreeNode {
    int val = 0;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
